1. Field of the Invention
The present invention relates to an image processing method and apparatus and, more particularly, to an image processing method and apparatus, which can paint out a portion inside a closed contour constituted by a plurality of line elements.
2. Related Background Art
In an apparatus of this type, to paint out a portion inside a closed area is a fundamental image processing function, and various paint out methods have been developed so far.
In the most fundamental method, a paint out range is sequentially instructed in units of pixel lines of a random-access memory (RAM) by software, and line pixels within the instructed range are painted out.
A typical example of such a method is described in an article "Fundamentals of Interactive Computer Graphics" (written by J. D. FOLEY/A. VAN DAM, published by Addison-Wesley, 1982, pp. 456 to 460).
This method will be briefly described below.
As for a closed figure F1 given by a top data string, as shown in FIG. 2A, bucket data (FIG. 3) of edges e1 to e10 constituting the figure are generated, and are arranged in the form of an edge table (ET) shown in FIG. 4. At this time, horizontal edges are excluded, and bucket data of only non-horizontal edges are generated. The edge table (ET) has pointer bucket tables Ay0 to Ayn (when an image consists of (n+1) rasters from a 0th raster to an nth raster), the number of which is equal to the number of scan line rasters that can be stored in an image memory. The bucket data of non-horizontal ones of the edges e1 to e10 are connected to the pointer bucket tables each corresponding to a y coordinate value of an edge point having a smaller y coordinate value in a list structure. When a plurality of bucket data form a list structure from the same pointer bucket table, these bucket data are sorted in the ascending order of x values (xmin) of their edge points having smaller y coordinate values, thereby forming the list structure. The pointer bucket table having no corresponding edge bucket data stores a marker code X indicating this. When a y coordinate value is not a minimal or maximal value in the y direction of an edge, a position advanced by one scan from an original y coordinate value along the corresponding edge is determined as an edge point having a smaller y coordinate value so as not to cause a judgement error in a figure element inside/outside judgment, and the edge table (ET) is generated based on this point. In FIG. 2A, an edge point B of the edge e3, an edge point I of the edge e9, and an edge point G of the edge e8 correspond to such points.
Edge bucket data Ae1 to Ae10 corresponding to the edges store y values (ymaxe1 to ymaxe10) of edge points having larger y coordinate values of the corresponding edges e1 to e10, x values (xmine1 to xmine10) of edge points having smaller y coordinate values of the edges, increments (.DELTA.xe1 to .DELTA.xe10) of x coordinate values obtained when the corresponding y coordinate values are increased by one, and pointers (Pe1 to Pe10) for connecting the edge bucket data of edges whose edge points having the smaller y coordinate values have a common y coordinate value in the ascending order of power from edge bucket data having a smaller x coordinate value. .lambda. in the pointers Pe1 to Pe10 means that there is no edge bucket to be connected any more (FIG. 3).
Note that the x direction coincides with a scan line direction (the right direction in FIG. 2A), and the y direction coincides with an increment direction (the downward direction in FIG. 2A) of scan lines.
Paint out processing is executed by utilizing the edge table (ET) generated in this manner. A scan line y coordinate value is set to be a minimum y coordinate value having edge bucket data in the edge table (ET). The edge bucket data are connected in association with the set scan line y coordinate value, thereby initializing an active edge table (AET; FIG. 5) to an empty state.
Thereafter, the following processing is repeated until both the active edge table (AET) and the edge table (ET) become empty.
(1) A new active edge table (AET) for connecting the edge bucket data associated with the scan line y coordinate value is formed by combining information of the edge table (ET) and information of the active edge 10 table (AET) at that time, while maintaining the sort order of x coordinate values (xmin) of the active edge table (AET).
(2) Two each of edge bucket data having smaller x coordinate values (xmin) of the active edge table (AET) are paired, a section therebetween is determined as a paint out section in a figure element, and paint out processing inside the section is executed.
(3) Edge bucket data having the scan line y coordinate value as a y value (ymax) of an edge point having a larger y coordinate value is deleted from the active edge table (AET) for an operation on the next scan line.
(4) The x coordinate values (xmin) of edge bucket data remaining in the active edge table (AET) are updated by utilizing increment data (.DELTA.x) for an operation on the next scan line. More specifically, a new xmin is obtained by xmin+.DELTA.x.
(5) After the x coordinate values (xmin) are updated, the edge bucket data are re-sorted on the basis of the updated x coordinate values (xmin).
(6) The scan line y coordinate value is incremented, and the control returns to the processing (i).
In this manner, paint out processing is executed. FIG. 5 shows the active edge table (AET) associated with the figure F1 shown in FIG. 2A when the scan line 10 y coordinate value is "14". FIG. 6 shows a transition of the state of the active edge table (AET) for the respective scan line y coordinate values (0 to 19).
Besides the above-mentioned method, various other methods for performing paint out processing at high speed by hardware have been proposed.
In a method of this type, after only pixels defining a contour of a figure are sketched on an image memory, the image memory is raster-scanned, so that paint out processing is started from an odd-numbered contour line dot on a scan line, and is ended at an even-numbered contour line dot (to be referred to as an odd-even inversion method hereinafter).
However, when the odd-even inversion method is used, if a contour is simply sketched, portions not to be painted out (e.g., L1, L2, L3, L4, and L5 in FIG. 7) are undesirably painted out, and a portion to be painted out (a broken line portion on the line L3) is left unpainted.
A proposal that sets contour sketch rules based on the above-mentioned drawback to improve the above-mentioned method is known.
For example, Japanese Patent Publication No. 1-54752 discloses a contour pixel write technique according to the following five rules.
Rule 1: Do not write a horizontal line segment; PA1 Rule 2: Express each line segment by one pixel per line; PA1 Rule 3: Do not write the start point of each line segment; PA1 Rule 4: EX-OR a contour line pixel and pixel data stored at a memory address at which this pixel is to be written, and write the EX-ORed result; and PA1 Rule 5: Instruct line segments in one direction, e.g., in a downward direction or a an upward direction.
The rule 1 prevents formation of an odd number of contour pixels in one line by contour pixels P1 and P2, and P4 and P3 included in horizontal contour line portions such as lines L2 and L4 in FIG. 7.
The rule 2 is to always represent a contour line by one pixel per line regardless of the angle of a line segment.
The rule 3 is to remove an upward or downward top. When line segments are instructed in one direction, e.g., a downward direction according to the rule 5, the rule 3 removes contour line pixels P5 and P6 as upward tops in FIG. 7.
The rules 4 and 5 remove a contour line pixel (P7 in FIG. 7) of a top in a direction opposite to the top processed according to the rule 3.
However, in the former prior art, i.e., in the 10 software method, since not only designation of a paint out range but also execution of a paint out operation itself are performed by software, the processing time becomes too long. FIG. 8 shows the processing result of the figure F1 shown in FIG. 2A by this conventional method. Like in a section between P2 and P1 in FIG. 8, points on the horizontal edge are often left unpainted, resulting in distortion of a generated figure.
In the latter prior art, i.e., in the method of performing paint out processing at high speed by hardware, the paint out execution speed can be higher than that in the former method. However, since all the contour lines must be sketched first, an image memory having a size corresponding to the entire image is required, resulting in high cost. FIG. 9B shows a result obtained by determining the paint out range of the figure F1 (FIG. 2A) by the conventional method (latter), and executing the paint out operation by a method recommended in the above-mentioned patent publication. However, in this method, top pixels such as P5 and P7 in FIG. 9B, and portions such as sections between P5 and P8, between P9 and P10, between P11 and P3, and between P12 and P7 are left unpainted, resulting in distortion of a generated figure.
In order to compensate for the distortion of the figure generated by the conventional methods, a method for additionally sketching only contour lines, and logically ORing the contour line pixels and the distorted figure pixels in units of pixels so as to output a figure free from distortion, as shown in, e.g., FIG. 10, is also attempted. In this case, however, a memory capacity required for processing is increased by a capacity for holding only the contour lines in addition to a memory on which the figure is generated, and an extra time and circuit for generating an image of only contour lines are required.
However, in the above-mentioned method, top pixels and some horizontal portions are left unpainted, and a distorted figure is reproduced. In the above-mentioned patent publication, after the contour line pixels are written, when lines on the memory are scanned to paint out from an odd-numbered contour line pixel to the next even-numbered contour line pixel, if the paint out operation is not started from the even-numbered contour line pixel according to the method recommended in the above-mentioned patent publication, pixels on the right contour line of the figure are deleted, and a figure smaller by one size than an original figure is reproduced.
FIG. 9A shows a case wherein the contour is sketched according to the above-mentioned rules. FIG. 9B shows a painted out result of the figure obtained, as shown in FIG. 9A, by the method recommended in the above-mentioned patent publication. In FIG. 9A, "x" marks indicate pixels which are not written as contour line pixels. In FIG. 9B, top pixels P5 and P7 are not painted, and a horizontal line between P1 and P2 is not painted out. When the figure is painted out by the recommended method, sections between P5 and P8, between P9 and P10, between P11 and P3, and between P12 and P7 are not painted out.
Japanese Laid-Open Patent Application No. 2-50778 discloses a method, which sets rules for determining whether or not pixels corresponding to points at two ends of a horizontal line (including a portion of continuous horizontal pixels generated upon sketching of an oblique line) is sketched in a contour sketch operation. However, this method has no disclosure about processing of top pixels, and does not consider a judgment error or distortion caused at the top pixels.
In order to compensate for the distortion of the figure generated by the conventional methods, a method for additionally sketching only contour lines, and logically ORing the contour line pixels and the distorted figure pixels in units of pixels so as to output a figure free from distortion is also attempted. In this case, however, a memory capacity required for processing is increased by a capacity for holding only the contour lines in addition to a memory on which the figure is generated, and an extra time and circuit for generating an image of only contour lines are required (see FIG. 30).
However, in the above-mentioned method, a distorted figure is reproduced. After the contour line pixels are written, when lines on the memory are scanned to paint out from an odd-numbered contour line pixel to the next even-numbered contour line pixel, if the paint out operation is not started from the even-numbered contour line pixel, pixels on the right contour line of the figure are deleted, and a figure smaller by one size than an original figure is reproduced.
FIG. 9A shows a case wherein the contour is sketched according to the above-mentioned rules. FIG. 9B shows a painted out result of the figure obtained in FIG. 9A. In FIG. 9A, "x" marks indicate pixels which are not written as contour line pixels. When the figure is painted out by the method recommended in the prior art, sections between P5 and P8, between P9 and P10, between P11 and P3, and between P12 and P7 are not painted out.
Japanese Laid-Open Patent Application No. 2-50778 discloses a method, which sets rules for determining whether or not pixels corresponding to points at two ends of a horizontal line (including a portion of continuous horizontal pixels generated upon sketching of an oblique line) is sketched in a contour sketch operation. However, this method has no disclosure about processing of top pixels, and does not consider a judgment error or distortion caused at the top pixels.
In order to compensate for the distortion of the figure generated by the conventional methods, a method for additionally sketching only contour lines, and logically ORing the contour line pixels and the distorted figure pixels in units of pixels so as to output a figure free from distortion, as shown in, e.g., FIG. 7, is also attempted. In this case, however, a memory capacity required for processing is increased by a capacity for holding only the contour lines in addition to a memory on which the figure is generated, and an extra time and circuit for generating an image of only contour lines are required.
Still another background art will be described below.
As for a closed figure F1 given by a top data string, as shown in FIG. 64A, bucket data (FIG. 65) of edges e1 to e13 constituting the figure are generated, and are arranged in the form of an edge table (ET) shown in FIG. 66. At this time, horizontal edges are excluded, and bucket data of only non-horizontal edges are generated. The edge table (ET) has pointer bucket tables Ay0 to Ayn (when an image consists of (n+1) rasters from a 0th raster to an nth raster), the number of which is equal to the number of scan line rasters that can be stored in an image memory. The bucket data of non-horizontal ones of the edges e1 to e13 are connected to the pointer bucket tables each corresponding to a y coordinate value of an edge point having a smaller y coordinate value in a list structure. When a plurality of bucket data form a list structure from the same pointer bucket table, these bucket data are sorted in the ascending order of x values (xmin) of their edge points having smaller y coordinate values, thereby forming the list structure. The pointer bucket table having no corresponding edge bucket data stores a marker code .lambda. indicating this. When a y coordinate value is not a minimal or maximal value in the y direction of an edge, a position advanced by one scan from an original y coordinate value along the corresponding edge is determined as an edge point having a smaller y coordinate value so as not to cause a judgement error in a figure element inside/outside judgment, and the edge table (ET) is generated based on this point. In FIG. 64A, an edge point C of the edge e3, an edge point M of the edge e12, and an edge point L of the edge e11 correspond to such points.
Edge bucket data Ae1 to Ae13 corresponding to the edges store y values (ymaxe1 to ymaxe13) of edge points having larger y coordinate values of the corresponding edges e1 to e13, x values (xmine1 to xmine13) of edge points having smaller y coordinate values of the edges, increments (.DELTA.xe1 to .DELTA.xe13) of x coordinate values obtained when the corresponding y coordinate values are increased by one, and pointers (Pe1 to Pe13) for connecting the edge bucket data of edges whose edge points having the smaller y coordinate values have a common y coordinate value in the ascending order of power from edge bucket data having a smaller x coordinate value. .lambda. in the pointers Pe1 to Pe13 means that there is no edge bucket to be connected any more (FIG. 65).
Note that the x direction coincides with a scan line direction (the right direction in FIG. 64A), and the y direction coincides with an increment direction (the downward direction in FIG. 64A) of scan lines.
Paint out processing is executed by utilizing the edge table (ET) generated in this manner. A scan line y coordinate value is set to be a minimum y coordinate value having edge bucket data in the edge table (ET). The edge bucket data are connected in association with the set scan line y coordinate value, thereby initializing an active edge table (AET; FIG. 67) to an empty state.
Thereafter, the following processing is repeated until both the active edge table (AET) and the edge table (ET) become empty.
(1) A new active edge table (AET) for connecting the edge bucket data associated with the scan line y coordinate value is formed by combining information of the edge table (ET) and information of the active edge table (AET) at that time, while maintaining the sort order of x coordinate values (xmin) of the active edge table (AET).
(2) Two each of edge bucket data having smaller x coordinate values (xmin) of the active edge table (AET) are paired, a section therebetween is determined as a paint out section in a figure element, and paint out processing inside the section is executed.
(3) Edge bucket data having the scan line y coordinate value as a y value (ymax) of an edge point having a larger y coordinate value is deleted from the active edge table (AET) for an operation on the next scan line.
(4) The x coordinate values (xmin) of edge bucket data remaining in the active edge table (AET) are updated by utilizing increment data (.DELTA.x) for an operation on the next scan line. More specifically, a new xmin is obtained by xmin+.DELTA.x.
(5) After the x coordinate values (xmin) are updated, the edge bucket data are re-sorted on the basis of the updated x coordinate values (xmin).
(6) The scan line y coordinate value is incremented, and the control returns to the processing (1).
In this manner, paint out processing is executed. FIG. 67 shows the active edge table (AET) associated with the figure F1 shown in FIG. 64A when the scan line y coordinate value is "14". FIG. 68 shows a transition of the state of the active edge table (AET) for the respective scan line y coordinate values (0 to 19).
Besides the above-mentioned method, various other methods for performing paint out processing at high speed by hardware have been proposed.
In a method of this type, after only pixels defining a contour of a figure are sketched on an image memory, the image memory is raster-scanned, so that paint out processing is started from an odd-numbered contour line dot on a scan line, and is ended at an even-numbered contour line dot (to be referred to as an odd-even inversion method hereinafter).
However, when the odd-even inversion method is used, if a contour is simply sketched, portions not to be painted out (e.g., L1, L2, L3, L4, L5, and L6 in FIG. 69) are undesirably painted out, and portions to be painted out (broken line portions on the lines L3 and L4) are left unpainted.
A proposal that sets contour sketch rules based on the above-mentioned drawback to improve the above-mentioned method is known.
For example, Japanese Patent Publication No. 1-54752 discloses a contour pixel write technique according to the above-mentioned five rules.
The rule 1 prevents formation of an odd number of contour pixels in one line by contour pixels at positions between P10 and P9, between P11 and P1, and between P4 and P3 included in horizontal contour line portions such as lines L2 and L4 in FIG. 69.
The rule 2 is to always represent a contour line by one pixel per line regardless of the angle of a line segment.
The rule 3 is to remove an upward or downward top. When line segments are instructed in one direction, e.g., a downward direction according to the rule 5, the rule 3 removes contour line pixels P5 and P6 as upward tops in FIG. 69.
The rules 4 and 5 remove contour line pixels (P7 and P8 in FIG. 69) of a top in a direction opposite to the top processed according to the rule 3.
However, in the former prior art, i.e., in the software method, since not only designation of a paint out range but also execution of a paint out operation itself are performed by software, the processing time becomes too long. FIG. 70 shows the processing result of the figure F1 shown in FIG. 64A by this conventional method. Like in a section between P2 and P1 in FIG. 70, points on the horizontal edge are often left unpainted, resulting in distortion of a generated figure.
In the latter prior art, i.e., in the method of performing paint out processing at high speed by hardware, the paint out execution speed can be higher than that in the former method. However, since all the contour lines must be sketched first, an image memory having a size corresponding to the entire image is required, resulting in high cost. FIG. 71 shows a result obtained by determining the paint out range of the figure F1 (FIG. 64A) by the conventional method (latter), and executing the paint out operation by a method recommended in the above-mentioned patent publication. However, in this method, top pixels such as P5 and P8 in FIG. 71, and portions such as sections between P5 and P10, between P9 and P10, between P9 and P15, between P11 and P1, between P1 and P12, between P13 and P3, and between P14 and P8 are left unpainted, resulting in distortion of a generated figure.
In order to compensate for the distortion of the figure generated by the conventional methods, a method for additionally sketching only contour lines, and logically ORing the contour line pixels and the distorted figure pixels in units of pixels so as to output a figure free from distortion, as shown in, e.g., FIG. 72, is also attempted. In this case, however, a memory capacity required for processing is increased by a capacity for holding only the contour lines in addition to a memory on which the figure is generated, and an extra time and circuit for generating an image of only contour lines are required.